package com.aaron.leetcode.lc05;

/**
 * @author liurong
 * @date 2022/1/21 18:43
 * @version:
 */

class Solution05_3 {

    /*
        回文串少有的动态规划不是最优方法的问题
        寻找回文串的问题核心思想是：从中间开始向两边扩散来判断回文串
     */

    public String longestPalindrome(String s) {
        //leetcode submit region begin(Prohibit modification and deletion)
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 以 s[i] 为中心的最长回文子串
            String s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2 = palindrome(s, i, i + 1);
            // res = longest(res, s1, s2)
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    String palindrome(String s, int l, int r) {
        // 防止索引越界
        while (l >= 0 && r < s.length()
                && s.charAt(l) == s.charAt(r)) {
            // 向两边展开
            l--; r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substring(l + 1, r);
    }

    public static void main(String[] args) {
        Solution05_3 solution05_3 = new Solution05_3();
        String s = "au";
        System.out.println(solution05_3.longestPalindrome(s));
    }


}

